The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Two recursive sets A and B form a minimal pair with respect to some polynomial time reducibility notion ≤pr if neither A nor B can be computed in polynomial time but every set which reduces to both A and B is polynomial time computable. We show that for every recursive set A∉P there is a recursive set B such that A and B form a minimal pair. Moreover, similar results for pairs without greatest predecessors...
The purpose of this paper is to draw attention to existential fixed-point logic. Among other things, we show that: (1) If a structure A satisfies an existential fixed-point formula φ, then A has a finite subset F such that every structure B with A|F = B|F satisfies φ. (2) Using existential fixed-point logic instead of first-order logic removes the expressivity hypothesis in Cook's completeness theorem...
The paper presents a general method by which various natural decision problems for programs in PROLOG and extensions of PROLOG can easily be shown to be recursively unsolvable. A particularly interesting application of this method gives an affirmative answer to Flannagan's [1985] conjecture that the floundering property for queries with respect to MU-PROLOG programs is undecidable.
Define a (∀1, unary)-sentence to be a prenex first-order sentence of unary type with only one (universal) quantifier. A successor structure is a structure 〈B,S〉 such that S is a function which is a permutation of the basis B with only one cycle. We exhibit a (∀1, unary)-sentence ϕ of type {S,U1,...,Up} such that if B is finite then 〈B,S〉 is a successor structure iff 〈B,S〉 satisfies ∃U1...∃Up ϕ. It...
Separation theorems are essential in complexity theory: looking for strict lower and upper bounds makes sense only in the context of a hierarchy theorem. For probabilistic complexity classes with deterministically constructible bounds the standard diagonalization techniques can be applied and yield at least as dense hierarchies as in the deterministic case. For Monte Carlo (i.e. bounded error probability)...
In this paper we study query and update operations for databases consisting of propositional clauses in definite Horn form. We assume that the operations are independent of the given form of the formula, i.e. operations applied to equivalent formulas result equivalent formulas. In order to estimate the required space and time we prove complexity bounds for each of the introduced operations. Finally...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.